package io.gimo.study.design_pattern.factory.abstract_factory.product;


import io.gimo.study.design_pattern.factory.abstract_factory.Sortor;

import java.util.Arrays;

public class QuickSortor implements Sortor {

	@Override
	public void sort(int[] target) {
		if (target.length > 0) {
			sort(target, 0, target.length - 1);
			System.out.println(Arrays.toString(target));
		}
	}

	private void sort(int[] target, int min_pos, int max_pos) {
		if (min_pos < max_pos) {
			// 获取哨兵值的位置
			int sentineValue = getSentinelValuePosition(target, min_pos, max_pos);
			// 比较前半部分
			sort(target, 0, sentineValue - 1);
			// 比较后半部分
			sort(target, sentineValue + 1, max_pos);
		}
	}

	private int getSentinelValuePosition(int[] target, int min_pos, int max_pos) {
		int sentineValue = target[min_pos];
		while (min_pos < max_pos) {
			// 从右往左选择比哨兵值小的元素的下标
			while (min_pos < max_pos && target[max_pos] >= sentineValue)
				max_pos--;
			target[min_pos] = target[max_pos];
			// 从左往右选择比哨兵值大的元素的下标
			while (min_pos < max_pos && target[min_pos] <= sentineValue)
				min_pos++;
			target[max_pos] = target[min_pos];
		}
		target[min_pos] = sentineValue;
		return min_pos;
	}

}
